package nowcoder

/*描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。
也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，
那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0<=n<=10000
进阶：时间复杂度O(n)，空间复杂度O(n)*/
func duplicate(numbers []int) int {
	// write code here
	for index := 0; index < len(numbers); {
		// 下标与该下标的数值不等
		if numbers[index] != index {
			// 先看一下当前值对应的下标是否已经有正确的对应数值
			if numbers[index] == numbers[numbers[index]] {
				return numbers[index]
			}
			// 如果不是对应的，则交换数值
			numbers[index], numbers[numbers[index]] = numbers[numbers[index]], numbers[index]
		} else {
			index++
		}
	}
	return -1
}
